#include "algo_dynamique.hh"
#include <fstream>
#include "structs.hh"

knapsack_dynamic::knapsack_dynamic(const string& filename){
  nombre_BTS = -1;
  capacite = -1;

  unsigned long tmp;

  ifstream inputStream ( filename.c_str(), ifstream::in ); 

  inputStream >> nombre_BTS;
  inputStream >> capacite;


  a = new vector<unsigned long> (nombre_BTS+1);
  r = new vector<unsigned long> (nombre_BTS+1);

#ifndef BENCHMARK
  cout << "nombre BTS: " << nombre_BTS << " capacite: " << capacite << endl <<endl;
#endif

  if( inputStream ) 
  {
    for(unsigned long i = 1; i <= nombre_BTS; ++i) 
    {
      inputStream >> tmp; //i

#ifndef BENCHMARK
      cout << "i" << i;
#endif

      inputStream >> tmp; //ri

#ifndef BENCHMARK
      cout << " ri:" << tmp;
#endif

      (*r)[i]=(tmp);
      inputStream >> tmp; //ai

#ifndef BENCHMARK
      cout << " ai:" <<tmp <<endl;
#endif

      (*a)[i]=(tmp);      
    }
  }
  inputStream.close();
}



knapsack_dynamic::~knapsack_dynamic(){
  delete a;
  delete r;
}



void knapsack_dynamic::run()
{
  unsigned long x_size = capacite+1;
  unsigned long y_size = nombre_BTS+1;
  BTS = new vector<unsigned long>( (x_size)*(y_size));
  vector <unsigned long> sol;

  unsigned long tmp1, tmp2;

  //BTS[0,w]=0
  for (unsigned int i = 0; i < y_size; ++i){
    (*BTS)[i*x_size]=0;
  }

  //BTS[i,0]=0
  for (unsigned int w = 0; w < x_size; ++w){
    (*BTS)[w]=0;	
  }


  //construit le tableau dynamique
  for (unsigned int i = 1; i < y_size; ++i){
    for (unsigned int w = capacite; w > 0; --w){ 
      checkTime();
      tmp1 = (*BTS)[ ( (i-1) * x_size ) + w ];

      if ( (*a)[i] > w ){
        (*BTS)[ (i*x_size) + w ] = tmp1; //m[i,w] = m[i-1,w]
      }else{
        tmp2 = (*BTS)[ ( (i-1) * x_size ) + ( w - ( (*a)[i] ))] + (*r)[i]; //m[i,w] = m[i-1,w-wi] + ri
        if ( tmp1 >= tmp2 ){
          (*BTS)[ (i*x_size) + w] = tmp1;
        }else{		  
          (*BTS)[ (i*x_size) + w] = tmp2;
        }  
      }
    }  
  }

  //lit le tableau dynamique pour trouver la solution
  unsigned int i = y_size-1;
  unsigned int w = x_size-1;
  while ( i > 0){  
    if ((*BTS)[(i*x_size)+w] != (*BTS)[ ((i-1)*x_size)+w ]){
      sol.push_back(i);
      w = w - (*a)[i];		
    }
    i=i-1;
  }

#ifndef BENCHMARK
  cout<< endl << "solution: ";

  for(vector<unsigned long>::iterator it = sol.begin(); it < sol.end();++it){
    cout<< *it << " ";
  }
#endif

  delete BTS;
}

int main(int argc, char** argv )
{
  if ( argc != 2 ) return 0;

  knapsack_dynamic kd = knapsack_dynamic(argv[1]);

#ifdef BENCHMARK
  startTimer();
#endif

  kd.run();

#ifdef BENCHMARK
  stopTimer();
#endif
  return 0;
}

